#include <vector>
#include <string>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <list>
using namespace std;

// 最长公共前缀
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string ret;
        int j = 0;
        while (true) {
            char ch = strs[0][j];
            int flag = 1;
            for (auto e : strs) {
                if (j == e.size() || e[j] != ch) {
                    flag = 0;
                    break;
                }
            }
            if (flag)
            {
                ret += ch;
                j++;
            }
            else
                break;
        }
        return ret;
    }
};

// 最长回文子串
class Solution {
public:
    string longestPalindrome(string s) {
        int begin = 0, len = 0, n = s.size();
        for (int i = 0; i < n; i++)
        {
            int left = i, right = i;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                left--;
                right++;
            }
            if (right - left - 1 > len)
            {
                len = right - left - 1;
                begin = left + 1;
            }
            left = i, right = i + 1;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                left--;
                right++;
            }
            if (right - left - 1 > len)
            {
                len = right - left - 1;
                begin = left + 1;
            }
        }
        return s.substr(begin, len);
    }
};

// 二进制求和
class Solution {
public:
    string addBinary(string a, string b) {
        string ret;
        int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0;
        while (cur1 >= 0 || cur2 >= 0 || t)
        {
            if (cur1 >= 0) t += a[cur1--] - '0';
            if (cur2 >= 0) t += b[cur2--] - '0';
            ret += (t % 2) + '0';
            t /= 2;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

// 字符串相乘
class Solution {
public:
    string multiply(string num1, string num2) {
        int n = num1.size(), m = num2.size();
        vector<int> arr(n + m - 1);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                arr[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }
        string ret;
        int k = 0;
        for (int i = n + m - 2; i >= 0; i--)
        {
            k += arr[i];
            ret += (k % 10) + '0';
            k /= 10;
        }
        if (k) ret += k + '0';
        reverse(ret.begin(), ret.end());
        if (ret.size() > 1 && ret.front() == '0') ret = '0';
        return ret;
    }
};